Search for: All records

Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents from their start locations to their goal locations without collisions. We study the lifelong variant of MAPF where agents are constantly engaged with new goal locations, such as in warehouses. We propose a new framework for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances, where a Windowed MAPF solver resolves collisions among the paths of agents only within a finite time horizon and ignores collisions beyond it. Our framework is particularly well suited to generating pliable plans that adapt to continually arriving new goal locations. We evaluate our framework with a variety of MAPF solvers and show that it can produce high-quality solutions for up to 1,000 agents, significantly outperforming existing methods. 

Abstract A workshop on The Next Generation Gamma-Ray Source sponsored by the Office of Nuclear Physics at the Department of Energy, was held November 17-19, 2016 in Bethesda, Maryland. The goals of the workshop were to identify basic and applied research opportunities at the frontiers of nuclear physics that would be made possible by the beam capabilities of an advanced laser Compton beam facility. To anchor the scientific vision to realistically achievable beam specifications using proven technologies, the workshop brought together experts in the fields of electron accelerators, lasers, and optics to examine the technical options for achieving the beam specifications required by the most compelling parts of the proposed research programs. An international assembly of participants included current and prospective γ -ray beam users, accelerator and light-source physicists, and federal agency program managers. Sessions were organized to foster interactions between the beam users and facility developers, allowing for information sharing and mutual feedback between the two groups. The workshop findings and recommendations are summarized in this whitepaper. 

We consider a variant of the Multi-Agent Path-Finding problem that seeks both task assignments and collision-free paths for a set of agents navigating on a graph, while minimizing the sum of costs of all agents. Our approach extends Conflict-Based Search (CBS), a framework that has been previously used to find collision-free paths for a given fixed task assignment. Our approach is based on two key ideas: (i) we operate on a search forest rather than a search tree; and (ii) we create the forest on demand, avoiding a factorial explosion of all possible task assignments. We show that our new algorithm, CBS-TA, is complete and optimal. The CBS framework allows us to extend our method to ECBS-TA, a bounded suboptimal version. We provide extensive empirical results comparing CBS-TA to task assignment followed by CBS, Conflict-Based Min-Cost-Flow (CBM), and an integer linear program (ILP) solution, demonstrating the advantages of our algorithm. Our results highlight a significant advantage in jointly optimizing the task assignment and path planning for very dense cases compared to the traditional method of solving those two problems independently. For large environments with many robots we show that the traditional approach is reasonable, but that we can achieve similar results with the same runtime but stronger suboptimality guarantees.